1. Field of the Invention
The present invention relates generally to a coding scheme and apparatus for the compression and decompression of data. It is particularly directed to the compression of signals that exhibit so-called memory, where a portion of a signal depends on the value of a preceding portion. The invention has particular application to medical systems, such as implantable pacemaker devices, which have limited memory but require the storage of large quantities of data.
2. Description of the Prior Art
Medical systems for monitoring physiological functions are becoming more complex as the need for diagnostic applications increases. In particular there is a need for intracardial detection systems and pacemaker systems capable of storing ever increasing numbers of signals, such as electrocardiogram signals (EGG and IEGM), pressure signals and bioimpedence signals or the like, of ever increasing length. However, the available memory space for data storage is often restricted, particularly in implanted pacemaker systems. Perhaps more importantly in implanted systems, the amount of data that may be collected is also restricted by the transmission capacity of a telemetry link between an implanted device and its programmer or other external control device. For example, a defibrillator today typically requires a transmission time of up to 40 minutes for downloading to its controller all the data that can be collected. If the required quantities of data are to be made available for processing, this data must be compressed.
Data compression can generally be divided into two forms. A first form is based on viewing a signal as a mathematical function and observing and utilizing characteristics of this function to compress data. The second form utilizes coding theory and is based on the statistics of multiple discrete signal levels, or symbols, occurring in a signal.
A conventional algorithm working according to this latter principle is the Tunstall code. This code maps variable-length symbol segments of an input signal into fixed-length codewords. Since the codeword length is fixed, the number of codewords n is known in advance. The object is to assign codewords to symbol segments that occur with approximately equal probability. The procedure begins with a set of symbol segments consisting of each of the individual symbols occurring in the input signal, such as m symbols in total. The most probable symbol is then removed from the set and replaced by m new segments, each of which is the removed symbol suffixed by one of the m input symbols. This procedure continues until the number of symbol segments, Manager, in the set is equal to the number of codewords, n. The codewords are then assigned to the symbol segments.
An example of Tunstall encoding is illustrated in FIGS. 1 and 2. FIG. 1 shows a probability tree comprising nodes, and branches emanating from each node. In the illustrated example it is assumed that S codewords are available for compressing data, 1 to 8. The tree in FIG. 1 assumes that a source signal comprises two signals, ‘0’ and ‘1’. Each symbol is represented by a first branch. The probability a symbol occurring is given at the node terminating the associated branch. Hence a ‘0’ occurs with a probability of 0.6 and a ‘1’ occurs with a probability of 0.4. The branch with the highest probability is expanded further by adding a second series of branches for each possible symbol. The ‘0’ branch is thus bifurcated into a second ‘0’ branch with a total probability of 0.36 and a ‘1’ branch with probability 0.24. The first branch for symbol ‘1’ now has the highest probability and is expanded in turn, resulting in two further branches with probability of 0.24 and 0.16. This process continues until the number of end branches equals the number of codewords, in the present example 8, with the probability of each branch occurring being relatively close. Each end branch represents a sequence of symbols. These sequences are assigned a codeword as shown in FIG. 2.
A problem associated with Tunstall encoding is that signals containing a large number of different symbols, for instance a large number of discrete signal levels, require a very large number of codewords. For example, in a pacemaker system, a typical electrogram or IEGM signal is represented by S bits sampled at 512 Hz. The number of symbols in this signal is thus 256. A Tunstall codebook for this signal would have to contain at least 256 codewords just to cover the different individual symbols. In order to obtain compression of the signal, the branches must be expanded further which adds a further 256 codewords per branch. The Tunstall code is a general-purpose data compression algorithm and is not adapted to special classes of data. In particular it is not effective when applied to signals which exhibit memory. Typically, many of the signals monitored by medical systems, and cardiac pacers in particular, exhibit some memory, one example being the IEGM signal. The use of Tunstall encoding for processing sampled data in medical systems, and specifically implanted systems, is thus limited.